package top100

func groupAnagrams(strs []string) [][]string {
	var exist = make(map[[26]int][]string)
	for i := 0; i < len(strs); i++ {
		var chars [26]int
		for j := 0; j < len(strs[i]); j++ {
			var idx = strs[i][j] - 'a'
			chars[idx]++
		}
		var newRes = exist[chars]
		newRes = append(newRes, strs[i])
		exist[chars] = newRes
	}
	var res [][]string
	for _, sames := range exist {
		res = append(res, sames)
	}
	return res
}

func lengthOfLongestSubstring(s string) int {
	var winMap = make(map[byte]int)

	var left = 0
	var max = 1
	for i := 0; i < len(s); i++ {
		if idx, ok := winMap[s[i]]; ok {
			if idx >= left {
				left = idx + 1
				winMap[s[i]] = i
			} else {
				winMap[s[i]] = i
				var diff = i - left + 1
				if diff > max {
					max = diff
				}
			}
		} else {
			var diff = i - left + 1
			if diff > max {
				max = diff
			}
			winMap[s[i]] = i
		}
	}
	return max
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	// 左中右
	var curNode = root
	var stack []*TreeNode
	var res []int
	for curNode != nil || len(stack) > 0 {
		for curNode != nil {
			stack = append(stack, curNode)
			curNode = curNode.Left
		}
		curNode = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, curNode.Val)
		curNode = curNode.Right
	}
	return res
}
func orangesRotting(grid [][]int) int {
	var rowQueue []int
	var colQueue []int
	var freshOranceCnt = 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 2 {
				rowQueue = append(rowQueue, i)
				colQueue = append(colQueue, j)
			} else if grid[i][j] == 1 {
				freshOranceCnt++
			}
		}
	}
	if freshOranceCnt == 0 {
		return 0
	}
	var cnt = -1
	for len(rowQueue) > 0 {
		cnt++
		var size = len(rowQueue)
		for i := 0; i < size; i++ {
			var iRow = rowQueue[i]
			var jCol = colQueue[i]
			// 上
			if isFreshOrange(grid, iRow-1, jCol) {
				grid[iRow-1][jCol] = 2
				freshOranceCnt--
				rowQueue = append(rowQueue, iRow-1)
				colQueue = append(colQueue, jCol)
			}
			// 下
			if isFreshOrange(grid, iRow+1, jCol) {
				grid[iRow+1][jCol] = 2
				freshOranceCnt--
				rowQueue = append(rowQueue, iRow+1)
				colQueue = append(colQueue, jCol)
			}
			// 左
			if isFreshOrange(grid, iRow, jCol-1) {
				grid[iRow][jCol-1] = 2
				freshOranceCnt--
				rowQueue = append(rowQueue, iRow)
				colQueue = append(colQueue, jCol-1)
			}
			// 右
			if isFreshOrange(grid, iRow, jCol+1) {
				grid[iRow][jCol+1] = 2
				freshOranceCnt--
				rowQueue = append(rowQueue, iRow)
				colQueue = append(colQueue, jCol+1)
			}
		}
		rowQueue = rowQueue[size:]
		colQueue = colQueue[size:]

	}
	if freshOranceCnt > 0 {
		return -1
	}
	return cnt
}

func isFreshOrange(grid [][]int, i, j int) bool {
	if i < 0 || i == len(grid) || j < 0 || j == len(grid[0]) || grid[i][j] != 1 {
		return false
	}
	return true
}

func isSubstringPresent(s string) bool {
	var existMap = make(map[string]bool)

	for i := 0; i < len(s)-1; i++ {
		existMap[s[i:i+2]] = true
		if existMap[string(s[i+1])+string(s[i])] {
			return true
		}
	}
	return false
}
func findMin1(nums []int) int {
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		if nums[left] <= nums[right] {
			return nums[left]
		}
		var mid = left + (right-left)/2
		if nums[mid] >= nums[left] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return -1
}

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	var dp = make([][]int, m+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if text1[i] == text2[j] {
				dp[i+1][j+1] = dp[i][j] + 1
			} else {
				dp[i+1][j+1] = getMax(dp[i][j+1], dp[i+1][j])
			}
		}
	}
	return dp[m][n]
}
